/*
https://leetcode.cn/problems/time-needed-to-inform-all-employees/description/
1376. 通知所有员工所需的时间
方钊堉 2024.11.6
dfs
*/

class Solution {
public:
    int numOfMinutes(int n, int _, vector<int> &managers, vector<int> &informTimes) {
        // 定义一个深度优先搜索函数来计算每个员工的通知时间
        function<int(int)> dfs = [&](int employee) -> int {
            if (managers[employee] >= 0) {
                // 如果当前员工的上级还没有被处理过
                informTimes[employee] += dfs(managers[employee]);
                managers[employee] = -1; // 标记当前员工的上级已处理
            }
            return informTimes[employee];
        };

        int totalTime = 0; // 用于记录总的最大通知时间
        for (int i = 0; i < n; ++i) {
            if (!informTimes[i]) {
                // 如果当前员工没有下属（即不需要通知任何人）
                totalTime = max(totalTime, dfs(i)); // 更新最大通知时间
            }
        }
        return totalTime;
    }
};